package string;

/**
 * 给你一个由小写英文字母组成的字符串 s 。
 * 请你找出字符串中两个字符 a1 和 a2 的出现频次之间的 最大 差值 diff = a1 - a2，这两个字符需要满足：
 * a1 在字符串中出现 奇数次 。
 * a2 在字符串中出现 偶数次 。
 * 返回 最大 差值。
 * <p>
 * 示例 1：
 * 输入：s = "aaaaabbc"
 * 输出：3
 * 解释：
 * 字符 'a' 出现 奇数次 ，次数为 5 ；字符 'b' 出现 偶数次 ，次数为 2 。
 * 最大差值为 5 - 2 = 3 。
 * <p>
 * 示例 2：
 * 输入：s = "abcabcab"
 * 输出：1
 * 解释：
 * 字符 'a' 出现 奇数次 ，次数为 3 ；字符 'c' 出现 偶数次 ，次数为 2 。
 * 最大差值为 3 - 2 = 1 。
 *
 * @author Jisheng Huang
 * @version 20250610
 */
public class MaxDifference_3442 {
    /**
     * 统计每种字母的出现次数 cnt。
     * 要让奇数减偶数尽量大，那么奇数要尽量大，偶数要尽量小。
     * 遍历所有出现次数 c=cnt[i]，计算：
     * 最大的奇数 c，记作 max1
     * 最小的正偶数 c，记作 min0
     *
     * @param s the given string
     * @return
     */
    public static int maxDifference(String s) {
        int[] cnt = new int[26];

        for (int c : s.toCharArray()) {
            ++cnt[c - 'a'];
        }

        int max1 = 0;
        int min0 = Integer.MAX_VALUE;

        for (int c : cnt) {
            if (c % 2 > 0) {
                max1 = Math.max(max1, c);
            } else if (c > 0) {
                min0 = Math.min(min0, c);
            }
        }

        return max1 - min0;
    }

    public static void main(String[] args) {
        System.out.println(maxDifference("aaaaabbc"));
        System.out.println(maxDifference("abcabcab"));
        System.out.println(maxDifference("mmsmsym"));
    }
}
